import javax.swing.tree.TreeNode;

public class BinaryTreeMathPathSum {
    public class TreeNode{
        int val;
        TreeNode left;
        TreeNode  right;
        public TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
    }
    int max =Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root){
        if (root == null) return 0;
        int left =maxPathSum(root.left);
        int right=maxPathSum(root.right);

        int nodeValue = Math.max(left, right) + root.val;

        max = Math.max(max,nodeValue);
        max = Math.max(max,left+right+ root.val);

        return  Math.max(0,nodeValue);
    }
}
